# 动态规划
# class Solution:
#     def minJump(self, jump) -> int:
#         n = len(jump)
#         ans = float('inf')
#         f = [n] * n
#         f[0] = 0
#         maxdis = [0] * n
#         min_curr_num = 0
#         for i in range(n):
#             if i > maxdis[min_curr_num]:
#                 min_curr_num += 1
#             f[i] = min(f[i], min_curr_num + 1)
#             next_jump = i + jump[i]
#             if next_jump >= n:
#                 ans = min(ans, f[i] + 1)
#             else:
#                 if f[next_jump] > f[i] + 1:
#                     f[next_jump] = f[i] + 1
#                     maxdis[f[i] + 1] = max(next_jump, maxdis[f[i] + 1])
#         return ans


# 广度优先搜索
class Solution:
    def minJump(self, jump):
        n = len(jump)
        visited_set = {0}
        st = [0]
        dist = 0
        far = 0
        while True:
            dist += 1
            next_st = []
            for idx in st:
                if idx + jump[idx] >= n:
                    return dist
                else:
                    if idx + jump[idx] not in visited_set:
                        visited_set.add(idx + jump[idx])
                        next_st.append(idx + jump[idx])
                    for index in range(far, idx):
                        if index not in visited_set:
                            visited_set.add(index)
                            next_st.append(index)
                    far = max(far, idx + 1)
            st = next_st





data = Solution()
jump = [5, 3, 5, 2, 5, 2, 2, 5, 5, 2, 5, 5, 1, 1, 3, 1, 2, 5, 1, 5, 2, 4, 1, 4, 2, 4, 4, 1, 3, 4, 5, 3, 1, 4, 4, 2]
print(data.minJump(jump))
